﻿/*
题目: 分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

https://www.acwing.com/problem/content/9/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

#define MAX_ITEM_NUM 103

int main() {
    int N, V;           // N 表示物品组数
    cin >> N >> V;

    vector<vector<int>> v(N + 1, vector<int>(MAX_ITEM_NUM + 1)), \
        w(N + 1, vector<int>(MAX_ITEM_NUM + 1));
    vector<int> c(N + 1);   // c[i] 表示第 i 组物品的个数
    for (int i = 1; i <= N; i++) {
        cin >> c[i];
        for (int j = 1; j <= c[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    // 表示选到第 i 个物品组的时候，体积为 v 的最大价值
    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0));
    int res = 0;
    for (int i = 1; i <= N; i++) {                      // 遍历每一组
        for (int j = V; j >= 1; j--) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);     // A> 不买

            // 或者从 分组商品 中选一个
            for (int z = 1; z <= c[i]; z++) {
                if (j >= v[i][z])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][z]] + w[i][z]);
            }
            res = max(res, dp[i][j]);
        }

    }

    std::cout << res << std::endl;
}
